
\chapter {Introduzione}
\label{cap:introduzione}
\section {Definizione del  plagio}
Il problema dell'individuazione del plagio \`e presente in tutti quegli ambiti nei quali \`e possibile definire una propriet\`a intellettuale. Da sempre infatti nella letteratura, nella musica e nello sviluppo del software \`e stato necessario un organismo che permettesse di controllare quando un oggetto contenesse parti di un altro senza indicarne specificatamente la sorgente.
In ambito musicale ad esempio si \`e in presenza di un plagio nel momento in cui un brano \`e uguale ad un altro per otto\footnote{Il numero di otto note non trova riscontro nei testi legislativi Italiani, vale pertanto solo come indicazione di massima derivata dall'esperienza.} o pi\`u battute della melodia della canzone. Per quanto riguarda la letteratura, un  testo pu\`o essere definito plagiato nel momento in cui si verifica la presenza di paragrafi, sezioni o capitoli appartenenti ad una fonte esterna non espressamente citata nella bibliografia.
Risulta chiaro da questi esempi come nonostante l'idea che sta alla base del plagio sia facile da intuire, non \`e altrettanto facile darne una definizione precisa e valida in tutti i contesti. \`E proprio l'ampio campo di applicazione che rende difficile la formulazione di una definizione che colga tutte le sfumature possibili di questo concetto.
Molto spesso si usa la definizione data dalla Webster's Enciclopedy Dictionary la quale definisce il plagio come la 
\begin{quote}  
``unauthorized use of the language and the thougths of another author and the representation of them as one's own (Verco and Wise, 1997)''
\end{quote}
Nonostante questa definizione colga il concetto di plagio risulta essere troppo generica. 

In questo documento verr\`a affrontato il tema del plagio contestualizzandolo nell'ambito del software. Un buon punto di partenza per definire formalmente questo aspetto \`e la citazione di Manber il quale afferma che 
\begin {quote} 
``our goal is to identify files that came from the same source or contain parts that came from the same source (Manber, 1994)''
\end {quote}
l'obiettivo principale \`e l'identificazione di files che provengono dalla stessa sorgente o che contengono parti che provengono dalla stessa sorgente. Manber in questa citazione cerca pertanto di porre l'attenzione sul fatto che due files sono considerati plagiati nel momento in cui derivano interamente o parzialmente da una stessa fonte.

\section {Il plagio nell'ambito del software}
Da un'indagine condotta alla Duke University~(Bliwise, 2001) \`e risultato che tra tutti gli studenti frequentanti un corso di programmazione di computer, il~40\% ha ammesso di aver copiato parte di un programma senza citarne la sorgente,~l'11\% ha confessato di aver inserito, in un proprio codice, segmenti di programmi altrui senza apportarne nessuna modifica e il~9\% ha ammesso di aver utilizzato un programma di un altro studente. Questo fatto sta a dimostrare quanto sia alta l'incidenza di questo fenomeno all'interno di un ambito accademico. 

\`E bene precisare che il plagio non \`e riferito esclusivamente alla condivisione di codice tra due individui, \`e possibile infatti che uno stesso programmatore utilizzi parti di codice sorgente da lui scritte in un assegnamento futuro. Questo fenomeno, denominato \emph{``self-plagiarism''}, in determinate circostanze potrebbe essere classificato come scorretto. D'altro canto per\`o questo potrebbe avvenire come diretta conseguenza dell'applicazione di linguaggi orientati agli oggetti i quali tendono ad incentivare questa pratica favorendo cio\`e il \emph{riuso del codice.}

Anche nell'ambito professionistico pu\`o succedere che interfacce o funzionalit\`a di un programma vengano interscambiate tra aziende. Questa attivit\`a ha incidenza sul prezzo dello sviluppo del software, in particolare sulla parte di design di un'applicazione, in quanto risulta pi\`u difficile lo scambio di codice sorgente da parte di due software house.

Un'ulteriore precisazione va fatta sulla differenza tra un lavoro cooperativo eseguito in gruppo e la mera copiatura di codice sorgente. Nel primo caso si presume infatti una buona conoscenza del codice da parte di tutti gli sviluppatori. Questo in ambito accademico potrebbe risultare soddisfacente al raggiungimento di una valutazione positiva da parte dell'esaminatore. Nel secondo caso invece si presuppone che un programmatore copi del codice, ne applichi delle modifiche a livello prettamente sintattico, ma non comprenda con precisione il reale funzionamento. \`E importante tenere presente per\`o che uno dei principali obiettivi universitari \`e la preparazione ad un futuro lavoro professionistico nel quale la cooperazione e il lavoro di squadra assumono un ruolo fondamentale. \`E quindi a discrezione del docente-esaminatore stabilire quanta incidenza abbia il lavoro cooperativo al fine della valutazione.

\section{Riconoscimento automatico del plagio}
Gi\`a dagli inizi degli anni~'80 sono sorti i primi campi di ricerca che cercavano di formalizzare il problema del plagio per poter realizzare dei tool che permettessero di riconoscerlo automaticamente. 
La maggior parte di questi si basa sul fatto che l'informazione \`e altamente strutturata, per questo quindi risulta pi\`u semplice definire un criterio di comparazione.
Nell'ambito letterario, al contrario, si \`e in presenza di un codice \emph{grezzo}, senza una struttura ben definita sulla quale poter effettuare dei confronti. Nel caso del testo sono presenti capitoli, sezioni, paragrafi, frasi, queste a loro volta composte da soggetti, verbi, aggettivi, nonostante questo per\`o un confronto tra due file  si traduce nella verifica di quante parole consecutive coincidono nei due file in quanto non \`e possibile verificare ad un alto livello la semantica. 

Se l'informazione \`e strutturata come ad esempio nel caso di codice sorgente, risulta molto pi\`u efficace effettuare un confronto che vada a verificare quante parti di questa struttura coincidono nei due file. Nel caso di un programma scritto in linguaggio C, ad esempio \`e possibile effettuare un confronto tra il numero di funzioni presenti, il numero di linee di codice oppure il numero di operatori o di operandi.
Si capisce quindi come la strutturazione dell'informazione possa essere di ausilio ad un software che tenta di riconoscere quando due file sono soggetti a plagio, a questo livello infatti \`e possibile effettuare confronti di tipo lessicale (ad esempio per quanto riguarda il nome delle funzioni o delle variabili) come anche di tipo sintattico (andando a verificare ad esempio la struttura delle funzioni).
In questo contesto si capisce il motivo per cui \`e importante dare una definizione precisa al termine plagio. Se da un lato, infatti, \`e difficile contestualizzare il problema, dall'altro questo \`e necessario per poter realizzare un tool capace di riconoscere automaticamente quando questo accade.
La forte dipendenza dal contesto \`e un chiaro sintomo di come sia impossibile realizzare un tool che permetta di confrontare due oggetti di qualunque tipo. \`E impensabile che possa esistere uno stesso tool capace di verificare --- in modo efficace --- la presenza di plagio tra due file di testo o tra due file di codice sorgente. Come vedremo in seguito \`e altrettanto difficile pensare ad uno stesso tool in grado di confrontare correttamente linguaggi di programmazione diversi.

Si \`e parlato della differenza tra un lavoro collaborativo di due programmatori e la copiatura da parte di un soggetto poco motivato. Anche questo aspetto influenza il design di un tool per il riconoscimento automatico del plagio. Le modiche apportate a due file in queste circostanze sono infatti molto diverse: se nel secondo caso riguardano solo la disposizione delle funzioni, la ridenominazione delle variabili, l'inserimento di commenti all'interno del codice o di altre modifiche pi\`u prettamente lessicali, nel primo caso saranno molto pi\`u subdole in quanto si presuppone una buona conoscenza del codice da parte di entrambi gli sviluppatori. 

\`E stato detto comunque che non sempre il lavoro collaborativo deve essere considerato come sospetto, per questo \`e necessario trovare il giusto compromesso al fine di evitare di creare un tool troppo sospettoso che restituisca troppi risultati poco significativi.

Non \`e possibile classificare tutti possibili metodi con i quali un programma pu\`o essere trasformato in un altro con le stesse (o simili) funzionalit\`a. Nonostante questo Joy e Luck~\cite{Plagiarism_1999} hanno cercato di identificare le trasformazioni pi\`u frequenti:
\begin {itemize}
\item {\bf trasformazioni lessicali:} con lessicali si intendono quelle modifiche che possono essere eseguite mediante un editor di testo. Queste non richiedono nessuna conoscenza del linguaggio utilizzato dal programma:
\begin {itemize}
	\item aggiunta, modifica o rimozione di commenti;
	\item modifiche alla formattazione del testo;
	\item modifiche al nome degli identificatori;
	\item in linguaggi come FORTRAN, modifiche al numero di linea;
\end {itemize}
\item {\bf trasformazioni strutturali:} questo tipo di modifiche richiedono una sorta di conoscenza del programma, \`e necessario pertanto effettuare un parsing del codice sorgente per poterne ricavare la struttura. Queste trasformazioni sono altamente dipendenti dal linguaggio utilizzato:
\begin {itemize}
	\item modifiche ai loop (ad esempio un ciclo \texttt{do-while} pu\`o essere sostituito con un ciclo \texttt{for});
	\item if annidati possono essere sostituiti con istruzioni case o viceversa;
	\item modifiche all'ordine delle istruzioni, nel momento in cui queste non modificano il significato del programma;
	\item le chiamate a procedure possono essere sostituite con chiamate a funzioni e viceversa;
	\item le chiamate a procedure (o funzioni) possono essere sostituite con una copia del corpo della procedura (o funzione);
	\item modifiche all'ordine degli operandi (ad esempio $x < y$ pu\`o diventare $y > x$).
\end {itemize}
\end {itemize}
Come si pu\`o notare Joy e Luck effettuano una netta distinzione tra le modifiche di tipo lessicale e quelli di tipo strutturale. La prossima sezione di questo capitolo si occuper\`a di analizzare i tool esistenti suddividendoli tra quelli che utilizzano il conteggio degli attributi, quelli cio\`e che si basano su un'analisi del primo tipo di modifiche e quelli che effettuano una scansione del programma per identificarne la struttura ed effettuare la comparazione su di essa.

\section {Tecniche per il rilevamento automatico del plagio di software}
\subsection {Conteggio degli attributi}
Il primo tipo di tool che andremo ad analizzare sono quelli che si basano sul calcolo e la comparazione degli attributi. Questi software rappresentano il programma mediante un numero che definisce un'analisi quantitativa di qualche caratteristica. Ad esempio il numero di linee di codice pu\`o essere considerata una metrica molto semplice che pu\`o essere utilizzata come valore di riferimento nel confronto di programmi. Naturalmente pi\`u metriche possono essere combinate assieme al fine di creare una tupla che rappresenta il numero di occorrenze di ciascun attributo.

Questo tipo di analisi fornisce una rappresentazione del programma nel suo complesso, andando ad analizzare in modo piuttosto generico le caratteristiche dello stesso.
Nelle prossime sezioni verranno analizzati i tool che utilizzano questa tecnica senza descrivere in modo dettagliato gli algoritmi ma fornendo una visuale generica al fine di esporre le principali metriche utilizzate.

\subsubsection {Metriche di Halsted}
Il primo sistema per il rilevamento automatico conosciuto in letteratura \`e quello sviluppato da Ottestein~\cite{Ottenstein} il quale utilizzava le metriche del software di Halstead~\cite{Halstead} per determinare il livello di similarit\`a tra coppie di programmi. Queste metriche si basano su:
\begin {itemize}
\item $\eta_1$ = numero di operatori unici;
\item $\eta_2$ = numero di operandi unici; 
\item $N_1$ = numero di occorrenze per ciascun operatore;
\item $N_2$ = numero di occorrenze per ciascun operando.
\end {itemize}
Il sistema identificava come similari due programmi con lo stesso numero di $\eta_1$, $\eta_2$, $N_1$, $N_2$, demandando all'esaminatore un'ispezione pi\`u accurata. Questo sistema non offriva risultati abbastanza precisi, per questo successivi esperimenti sono stati effettuati utilizzando queste metriche insieme al conteggio del numero di cicli o procedure per riuscire a definire una migliore misura di similarit\`a. I sistemi basati sul conteggio degli attributi si sono via via raffinati per identificare con maggior precisione i casi sospetti.

\subsubsection {Accuse}
Il primo vero tool per verificare la similarit\`a di due programmi \`e Accuse, il quale utilizza sette parametri per la caratterizzazione di un programma:
\begin {itemize}
\item numero di operatori unici;
\item numero di operandi unici (ad esempio il numero di identificatori, di etichette, interi, reali, stringhe e nil);
\item numero totale di operatori;
\item numero totale di operandi;
\item numero di linee di codice (escludendo le linee vuote o di commento o di dichiarazioni);
\item variabili dichiarate e usate;
\item numero totale di istruzioni di controllo.
\end {itemize}
Accuse lavora in due fasi: nella prima viene calcolato il valore di tutte le sette metriche per ogni programma, nella seconda fase coppie di queste settuple sono confrontate per identificare il grado di similarit\`a tra due programmi. Questo dipender\`a dalla dimensione della finestra e l'importanza del parametro, valori che devono essere settati dall'utente per ogni metrica.
La dimensione della finestra rappresenta la massima differenza tra due valori di un parametro entro la quale si deve sospettare un plagio.
Il valore di importanza rappresenta la significativit\`a del parametro.
Il grado di similarit\`a viene calcolato nel seguente modo:
\begin {enumerate}
\item $\mathit{corr}_{AB} = 0 $
\item $\mathit{diff}_i = |A_i - B_i|$         per ogni metrica $i$ dei programmi $A$ e $B$
\item $\mathit{corr}_{AB} += \mathit{importanza}_i - \mathit{diff}_i $        se $\mathit{diff}_i \leq \mathit{finestra}_i $
\end {enumerate}
Inizialmente il grado di correlazione per una coppia di programmi $A$ e $B$ viene settato a 0, successivamente per ogni metrica viene calcolata la differenza nel seguente modo:
\[
\mathit{diff} = |A_i - B_i|
\]
dove $A_i$ \`e il valore della metrica $i$ per il programma $A$ e $B_i$ \`e il corrispondente valore per il programma $B$. Se questa differenza \`e minore o uguale al valore della finestra, la correlazione tra $A$ e $B$ viene incrementata di un valore pari a 
\[
\mathit{importanza}_i - \mathit{diff}_i
\]
Alla fine di questo calcolo tutti i valori di correlazione sono ordinati in ordine decrescente in modo che i programmi che sono pi\`u simili appaiano in cima ai risultati.

\subsubsection {Il sistema di Faidhi-Robinson}
Il sistema di Faidhi-Robinson tenta di diminuire la percentuale di falsi positivi utilizzando un set di metriche che gli autori reputano come minimale. Questo significa che nessuna metrica, nell'insieme delle $23$ utilizzate, \`e correlata con le altre.
Sono anche presenti delle caratteristiche che vengono definite nascoste le quali, secondo gli autori, rappresentano le modifiche che possono essere apportate al codice solo da un programmatore esperto.
Le prime $10$ metriche, quelle pi\`u frequentemente modificate da un programmatore poco esperto, sono quelle che rappresentano le caratteristiche pi\`u evidenti del testo di un programma e sono:
\begin{itemize}
\item numero medio di caratteri per linea;
\item numero di linee di commento;
\item numero di linee indentate;
\item numero di linee vuote;
\item lunghezza media delle procedure o funzioni;
\item numero di parole riservate;
\item lunghezza media degli identificatori;
\item percentuale media di spazi per linea;
\item numero di etichette e di goto;
\item numero di identificatori unici.
\end{itemize}
Il secondo gruppo di metriche, quelle che cercano di misurare le caratteristiche intrinseche e nascoste della struttura di un programma sono:
\begin{itemize}
\item numero di intervalli di un programma: per calcolare questo valore si utilizza l'algoritmo di Cocke e Allen che permette di partizionare il grafo di flusso di un programma in intervalli;
\item numero di vertici colorati con i colori base: il grafo di flusso di un programma viene colorato con un massimo di quattro colori, i colori base sono il primo e il secondo;
\item numero di vertici colorati con il colore 3;
\item numero di vertici colorati con il colore 4;
\item percentuale di espressioni di un programma: questa caratteristica basata sulla terminologia convenzionale utilizzata per descrivere la sintassi del Pascal, rappresenta il numero di espressioni come percentuale di tutte le espressioni, semplici espressioni, termini e fattori;
\item percentuale di espressioni semplici;
\item percentuale di termini;
\item percentuale di fattori;
\item numero delle impurit\`a del programma: ad esempio caratteri `;' superflui;
\item percentuale di incidenza di un modulo: questo valore rappresenta il numero di linee di codice all'interno di una funzione o una procedura rispetto al totale;
\item numero di moduli;
\item percentuale di istruzioni condizionali;
\item percentuale di istruzioni di ripetizione;
\item numero di istruzioni del programma.
\end {itemize}
Anche in questo software \`e necessario definire, per ogni metrica, il valore della finestra e l'importanza. A questo punto \`e possibile calcolare la similarit\`a di due programmi nel seguente modo:

\[
\mathit{increment}_i = {(\mathit{window}_i - \mathit{diff}_i) \over \mathit{window}_i } \times \mathit{importance}_i
\]
  
\subsection {Analisi della struttura}
Se da un lato un'analisi lessicale (\emph{piatta}) di un codice sorgente pu\`o risultare semplice ed efficace, dall'altro questa non tiene in considerazione di un aspetto molto  importante. I software che cercano di individuare le similarit\`a mediante l'analisi della sintassi identificano infatti \emph{la struttura di un codice sorgente} per poter essere quanto pi\`u insensibili a modifiche di tipo lessicale. L'obiettivo principale di questi software \`e l'astrazione dal nome degli identificatori o delle funzioni e l'analisi della composizione strutturale di un programma.
Questa tecnica seppur pi\`u efficace porta con s\'e degli importanti svantaggi. 

\`E necessario infatti conoscere il linguaggio di programmazione usato per poter effettuare la prima fase di scansione del programma, quella in cui si legge il codice sorgente e si crea una struttura intermedia. La naturale conseguenza di questa operazione \`e un aumento dei tempi di elaborazione per il calcolo delle similarit\`a.

L'algoritmo per il rilevamento degli elementi in comune, inoltre, avendo a che fare con una rappresentazione dei file composta da token tende generalmente ad aumentare il grado di similarit\`a tra due programmi. \`E importante pertanto strutturare bene l'algoritmo di confronto per non incorrere in falsi positivi.

Nelle prossime sezioni verranno analizzati i principali tool esistenti che effettuano questo tipo di confronti. Anche in questo caso verr\`a fornita una panoramica generale utile alla comprensione del funzionamento nel suo complesso.

\subsubsection {Sim}
SIM~\cite{Sim_1999} (Software Similarity Tester), sviluppato da Grune presso l'universit\`a di Vrije, permette di verificare la similarit\`a misurando le somiglianze lessicali di testi scritti in C, Pascal, Modula-2, Miranda o in linguaggio naturale.
Secondo gli autori questo software \`e in grado di rilevare il plagio e la duplicazione di frammenti di codice nei progetti software.

SIM opera in tre passi:
\begin {itemize}
\item Lettura del programma (passo uno): ogni file viene letto usando utilizzando uno scanner appropriato al linguaggio di programmazione utilizzato, i token di dimensione 1 byte sono memorizzati in un array.
\item Preparazione di una tabella forward-reference: Ogni sotto stringa di dimensione minima viene confrontata con tutte le altre alla sua destra, il risultato di questo \`e una tabella dove sono memorizzati gli indici delle sotto-stringhe successive che hanno lo stesso valore (0 se non vengono trovate).
\item Determinazione dell'insieme dei run interessanti: l'algoritmo analizzando tutti i files determina le sottostringhe uguali e di lunghezza massima
\item Determinazione del numero di linea del run (passo due): in questa fase viene ricercata la posizione del run identificato.
\item Presentazione dei risultati in ordine (passo tre): i risultati vengono forniti all'utente in ordine di importanza (lunghezza del run) assieme ai numeri di linea.
\end {itemize}
Ogni programma viene quindi rappresentato mediante una sequenza di token, successivamente queste sono confrontate tra loro al fine di individuare delle sotto sequenze (\emph {run}) in comune. A questo punto SIM restituisce come output in ordine decrescente, in base alla loro lunghezza, i run calcolati e la loro posizione nel testo.
L'analisi che viene effettuata \`e simile a quella per la ricerca delle stringhe del DNA.
In questo modo il programma riesce ad essere totalmente indifferente alla ridenominazione dei nomi, alla posizione delle istruzioni nel testo e all'aggiunta o la rimozione di spazi bianchi o commenti.

\subsubsection {Jplag}
Jplag~\cite{Jplag} \`e un software di rilevamento del plagio sviluppato da Tichy presso l'universit\`a di Karlsruhe che permette di analizzare files scritti in linguaggio C, C++, Java e Scheme. 
Jplag opera principalmente in due fasi:
\begin {itemize}
\item I programmi da confrontare sono riconosciuti e convertiti in stringhe composte da token. 
\item Queste stringhe vengono confrontate a coppie per identificare la similarit\`a. Durante ogni confronto, Jplag cerca di individuare una sequenza di token uguale ad una sottostringa ("tiles") presa dal secondo file.
\end {itemize}
Nella prima fase il programma viene convertito in una sequenza di token, a seconda del linguaggio utilizzato questo viene effettuato mediante uno scanner oppure mediante un parser, la principale differenza tra queste due tecniche \`e che nel secondo caso (utilizzato per i linguaggi Java e Scheme) \`e possibile ottenere maggiori informazioni di tipo semantico. Ad esempio \`e possibile creare un token \textit{BEGINMETHOD} piuttosto che un semplice \textit{OPEN\_BRACE} nel caso di un metodo Java.

Nella seconda fase di comparazione di due stringhe di token viene utilizzato l'algoritmo di ``Greedy String Tiling'' creato da Wise~\cite{GST}.
Nel confronto di due stringhe $A$ e $B$ si cerca cio\`e di individuare le sottostringhe in comune che soddisfano le seguenti regole:
\begin {itemize}
\item Ogni token della prima stringa deve essere uguale ad un token della seconda stringa. Questa regola permette di identificare parti di codice sorgente che sono state duplicate in un programma soggetto a plagio.
\item Le sottostringhe devono essere identificate indipendentemente dalla loro posizione nella stringa. Questa regola permette di identificare la situazione in cui le istruzioni (o parti di codice) vengono riordinate.
\item Hanno maggiore importanza le sottostringhe di lunghezza maggiore. Con questa regola si cerca di evitare match spuri (quelli cio\`e di minore importanza).
\end {itemize}

\subsubsection {Moss}
MOSS~\cite{Plagiarism_1996} (Measure of Software Similarity) \`e stato sviluppato nel 1994 da Aiken presso l'universit\`a di Berckeley. Permette di analizzare file scritti in C, C++, Java, Pascal, Ada, Ml, Lisp e Scheme. Questo strumento \`e disponibile apertamente online e permette, a partire da una lista di codici sorgenti, di ottenere una pagina HTML che elenca le coppie di programmi in ordine di similarit\`a.

Gli autori di questo strumento reputano che qualsiasi applicazione per il rilevamento del plagio debba soddisfare le seguenti tre propriet\`a:
\begin {itemize}
\item Indipendenza dagli spazi bianchi: La definizione di questa propriet\`a dipende da quale tipo di file bisogna confrontare. Nel caso dei file di testo ad esempio il tool dovrebbe essere insensibile a spazi vuoti, lettere maiuscole, punteggiatura, ecc. Nei software invece bisognerebbe astrarre dal nome delle variabili.
\item Soppressione del rumore: il rilevamento di stringhe molto corte all'interno di due file non deve essere significativo. Ad esempio la presenza di numerose congiunzioni all'interno di due file di testo non deve aumentare il livello di similitudine tra questi.
\item Indipendenza dalla posizione: un tool efficiente dovrebbe essere capace di individuare una porzione di testo indipendentemente dalla sua posizione.
\end {itemize}
MOSS rispetto a Jplag utilizza una tecnica denominata ``Winnowing''~\cite{Winnowing_2003} per il calcolo delle similitudini. Questa, dopo aver eliminato tutte le informazioni ininfluenti (ad esempio spazi o punteggiatura in un file di testo), divide la sequenza di caratteri cos\`i ottenuta in ``k-gramm'' ovvero sottostringhe di lunghezza fissa determinata dall'utente, le quali vengono poi codificate mediante una funzione hash al fine di creare il cosiddetto ``fingerprint'' del file.
A questo punto dopo aver trasformato in questo modo l'input, l'algoritmo di ``Karp-Rabin''~\cite{Karp-rabin} permette di effettuare il matching tra i $k$-gram.
Non \`e obiettivo di questa relazione entrare nei particolari di questa tecnica, per ulteriori informazioni si rimanda a~\cite{Winnowing_2003}.
 
\subsubsection {Conclusioni}
I sistemi che utilizzano l'attribute-counting per il calcolo della similarit\`a sono i primi ad essere stati sviluppati e pongono l'attenzione su un'analisi prettamente lessicale la quale, come gi\`a detto in precedenza, offre una visuale piuttosto generica dell'intero codice. Il problema principale di questi tool \`e l'impossibilit\`a di riconoscere tutte quelle modifiche che sono effettuate da un programmatore esperto. Possedere un buon bagaglio di conoscenze sulla programmazione permette infatti di effettuare modifiche non direttamente identificate da questi software. Un esempio pu\`o essere la sostituzione di una struttura dati con un'altra equivalente.
Nonostante si siano effettuati numerosi affinamenti a questi software fino ad arrivare al conteggio di 23 attributi, questi sistemi soffrono del problema di essere dipendenti, ad esempio, dal tipo di istruzioni utilizzate o dal nome delle variabili.
Inoltre come \`e stato possibile notare dalla descrizione, \`e necessaria una fase di tuning del sistema che permetta di settare i parametri della finestra e l'importanza di ciascun attributo nel modo pi\`u opportuno. Soprattutto l'importanza che si decide di assegnare ad una determinata feature risulta essere molto significativa al fine del calcolo dei risultati.
Non \`e poi cos\`i banale, per\`o, decidere di assegnare un valore di importanza ad un attributo rispetto ad un altro.
Il lato positivo di questo tipo di sistemi \`e che non necessitano di una pre-fase di analisi/strutturazione del codice sorgente. Questo permette di utilizzare un'unica applicazione per pi\`u tipi di linguaggio di programmazione (sintatticamente simili) e soprattutto ottenere una misura di similarit\`a in tempi veramente brevi. Questo aspetto \`e molto importante se si considera la principale applicazione di questo tipo di software ovvero il confronto simultaneo di tanti progetti i quali a loro volta contengono numerosi file di codice sorgente.


I software che sfruttano la struttura del programma per calcolare la similarit\`a necessitano di una fase di pre-analisi del codice sorgente che permetta di strutturare in modo opportuno l'informazione. Da questa fase \`e possibile ottenere numerose informazioni di tipo semantico le quali permettono di effettuare dei confronti pi\`u accurati rispetto ai metodi lessicali. Naturalmente se da un lato questo pu\`o essere considerato un aspetto positivo dall'altro implica la necessit\`a di strutturare in modo opportuno l'algoritmo di comparazione per evitare di entrare troppo nei dettagli e presentare molti risultati poco significativi. Un esempio di questo aspetto \`e l'attenzione che \`e necessario porre sulla lunghezza della sotto stringa identificata. 

La complessit\`a computazionale di questi programmi cresce esponenzialmente al crescere dei dati in ingresso (rispetto all'andamento lineare dei tool attribute-counting), nonostante questo la qualit\`a dei risultati ottenuti risulta essere, a livello sperimentale, tanto maggiore da giustificarne l'attesa.
In conclusione si pu\`o affermare che la strutturazione dell'informazione nella verifica della similarit\`a tra due programmi risulta essere la chiave principale per ottenere risultati soddisfacenti.

\section {Un nuovo  approccio}
Fino a questo punto abbiamo analizzato diversi approcci che cercavano di ottenere risultati sempre pi\`u accurati andando ad analizzare in dettaglio il linguaggio di programmazione utilizzato. Si \`e partiti da un'analisi prettamente lessicale di un documento per l'individuazione degli elementi principali che lo costituiscono per poi arrivare all'analisi della struttura di un codice sorgente in base al linguaggio di programmazione utilizzato. Si \`e cio\`e cercato di astrarre sempre pi\`u dall'analisi del testo per arrivare ad una analisi della sintassi che cercasse di individuare gli elementi costitutivi di un programma. Per fare questo \`e stato necessario specializzare il tool per il riconoscimento rendendolo di fatto altamente language-dependent.
L'idea che sta alla base del nostro programma \`e che questo dovr\`a andare ad analizzare dei linguaggi di tipo funzionale. Questo presupposto ci permette di eseguire un passo oltre l'analisi prettamente sintattica andando ad effettuare un confronto il pi\`u possibile rivolto alla semantica. Il nostro obiettivo \`e cio\`e quello di approssimare il problema indecidibile dell'individuazione della semantica di un programma e contestualizzarlo nell'ambito del confronto tra due progetti.
Alla base della nostra intuizione vi sono due presupposti. 
\begin {itemize}
\item un linguaggio fortemente tipato
\item l'inferenza dei tipi
\end {itemize}
Risulta essere di particolare importanza il fatto che il linguaggio debba essere fortemente tipato ovvero che non sia possibile una conversione non esplicita dei tipi in modo trasparente all'utente. Il linguaggio $\OCaml$ permette la conversione dei tipi solo se espressamente richiesta dall'utente.
Un ulteriore aspetto altrettanto importante \`e la capacit\`a del type checker\footnote{Il type checker \`e un modulo del compilatore che si occupa della verifica dei tipi assegnati alle variabili/funzioni.} di riuscire ad identificare un tipo anche se questo non \`e stato esplicitamente definito dall'utente. Questa situazione ci permette di essere a conoscenza dei tipi dei parametri e dei risultati di una funzione anche se questi non sono stati specificati.

Il nostro approccio vuole identificare un progetto andando ad analizzare i \emph{tipi} delle funzioni di cui \`e composto. Il confronto non \`e pi\`u basato sugli attributi o sulla struttura del programma, bens\`i si riduce al conteggio del numero di funzioni con tipi equivalenti all'interno di due progetti.

L'obiettivo \`e quello di approssimare il concetto di semantica di una funzione, il tipo ora rappresenta una parziale specifica della logica della stessa. Secondo la nostra intuizione, il fatto che una funzione operi, ad esempio, su due interi e restituisca un intero ci fornisce una descrizione approssimativa del suo funzionamento.

\`E chiaro come sia molto importante identificare in modo preciso il concetto di equivalenza di tipi. Il modo pi\`u semplice potrebbe essere quello di confrontarne la struttura, ovvero:
\[
\begin {split}
se:&\\
&f: \tint \to \tfloat \to \tbool\\
&g: \tint \to \tfloat \to \tbool  \\
allora:& \\
&f = g. \\        
\end {split}
\]
Se sono presenti due funzioni che prendono in ingresso un numero intero e uno in virgola mobile e restituiscono un valore booleano allora possiamo affermare con certezza che queste siano \emph{equivalenti}. 

Questa definizione di equivalenza, tuttavia, risulta essere troppo restrittiva in quanto si presuppone che un programmatore che copia del codice sorgente vi applichi delle modifiche. Se ad esempio queste modifiche riguardano l'ordine dei parametri di una funzione, il concetto di equivalenza espresso precedentemente non \`e sufficiente ad identificare il plagio.

\`E stato necessario pertanto identificare un metodo per comparare due funzioni il quale fornisse una relazione di equivalenza pi\`u lasca.

In bibliografia questo concetto \`e stato ritrovato nell'ambito degli isomorfismi di tipo~\cite{Deciding_1992, Type_1995}. I primi campi di ricerca che si sono sviluppati su questo argomento risalgono ai primi anni `80, anni nei quali Rittri, Bruce e Longo iniziarono a formalizzare il problema dell'individuazione di un metodo alternativo per la ricerca di funzioni in una libreria. Fino a quel momento le ricerche erano basate esclusivamente sul nome della funzione (o su sinonimi), si cerc\`o quindi di definire un criterio di equivalenza che potesse essere insensibile ad operazioni di ridenominazione, currying/uncurrying o di permutazione degli argomenti.\footnote{Nel seguito di questa tesi questi concetti verranno chiariti e descritti nel dettaglio.}

Il risultato di questi studi ha permesso di identificare un concetto di isomorfismo il quale permette di confrontare i tipi di due funzioni in questo modo:
\[
\begin {split}
se: & \\
&f: \tint \to \tfloat \to \tbool \\
&g: \tfloat \to \tint \to \tbool \\
allora:& \\
&f \cong g \\
\end {split}
\]
Come \`e chiaro da questo esempio gli isomorfismi in questo contesto permettono di definire una relazione di uguaglianza con un margine di differenze tra i tipi di una funzione.

Il primo problema che si \`e presentato durante la fase di analisi di fattibilit\`a del software \`e stato il timore che sotto queste condizioni tutti i progetti risultassero equivalenti (o pi\`u precisamente isomorfi). Si potrebbe pensare infatti, che andando ad astrarre cos\`i tanto il concetto di uguaglianza e in particolare di semantica di una funzione, si arrivi al punto in cui tutti i progetti sono uguali in quanto aderenti ad una stessa specifica. L'analisi dei codici sorgenti per\`o ha mostrato come, nonostante i progetti risolvessero tutti lo stesso problema, i tipi delle funzioni erano abbastanza differenti. Questo ci ha permesso di inferenziare che l'analisi dei tipi potesse funzionare.

\paragraph {Struttura della tesi}
Il capitolo~\ref{isomorfismi} di questa tesi affronter\`a il tema degli isomorfismi, verr\`a illustrato in modo formale cosa significa affermare che due tipi sono isomorfi, vedremo come sono caratterizzati gli isomorfismi che prenderemo in considerazione e verr\`a esposto il funzionamento dell'algoritmo che permette di identificarli. Il capitolo~\ref{architettura} si concentrer\`a sull'architettura del software realizzato descrivendone il funzionamento e mostrando alcuni esempi di utilizzo. Nel capitolo~\ref{conclusioni} verranno confrontati i risultati ottenuti mediante il nostro tool e quelli attualmente esistenti, andando ad analizzare i punti deboli e di forza del software prodotto.

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "tesi"
%%% End: 